package hot150;

// https://leetcode.cn/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150
public class q9 {

    public boolean canJump(int[] nums) {
        return method1(nums, nums.length);
    }

    /**
     * 贪心
     * 1 ms
     * 复杂度O(n)
     */
    public boolean method1(int[] nums, int n) {
        int max = nums[0];
        // 限制最远达到距离
        for (int i = 0 ; i <= max ; i++) {
            // 计算每一步的最大跳转距离
            max = Math.max(max, i + nums[i]);
            // 到或超出终点则返回true
            if (max >= n - 1) {
                return true;
            }
        }
        return false;
    }
}
